#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: three_nums_sum_double_points.py 
@version:
@time: 2023/12/28 
"""
array = [-1, 0, 1, 2, -1, -4]


def tree_sum(arr):
    # 排序
    arr.sort()
    # 初始化结果
    res = []
    # k只取0到n-2，l是n-1，r是n
    # k是三数的第一个
    # l是三数的第二个，左边的那个数
    # r是三数的第三个，右边的那个数
    for k in range(len(arr) - 2):
        # 因为arr已经排序，当第一个数大于零，那么后面的两个数肯定大于零，三数之和肯定都不能为0
        if arr[k] > 0: break
        # 如果当前元素和当前元素之前的元素值相同，那么就可以跳过本轮循环，因为res中一定已经存在了包含当前元素的和为0的三元组，跳过重复元素，提高效率。
        if k > 0 and arr[k] == arr[k - 1]: continue
        # l为k+1，r为数组长度-1
        l, r = k + 1, len(arr) - 1
        while l < r:
            # 计算三数之和
            s = arr[k] + arr[l] + arr[r]
            # 如果和小于0
            if s < 0:
                # l右移一位
                l += 1
                # 如果l<r并且后移后的l的值等于移动之前的值，l继续+1
                while l < r and arr[l] == arr[l - 1]: l += 1
            elif s > 0:
                # r左移一位
                r -= 1
                # 如果l<r并且前移后的r的值等于移动之前的值，r继续-1
                while l < r and arr[r] == arr[r + 1]: r -= 1
            else:
                # 如果s==0，将结果添加到res
                res.append([arr[k], arr[l], arr[r]])
                # 继续让左指针向右移动，右指针向左移动
                l += 1
                r -= 1
                # 在移动过程中再使用一个循环不断跳过重复元素
                while l < r and arr[l] == arr[l - 1]: l += 1
                while l < r and arr[r] == arr[r + 1]: r -= 1
    return res


if __name__ == '__main__':
    print(tree_sum(array))
